public class Leetcode {
}

//leetcode:2:两数相加
class Solution1 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null,tail = null;
        int carry = 0;
        while(l1 != null || l2 != null){
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if(head == null){
                head = tail = new ListNode(sum%10);
            }else{
                tail.next = new ListNode(sum%10);
                tail = tail.next;
            }
            carry = sum / 10;
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }
        if(carry > 0){
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

//leetcode:24：两两交换链表中的结点
class Solution2 {
    public ListNode swapPairs(ListNode head) {
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode cur = node;
        while(cur.next != null && cur.next.next != null){
            ListNode a = cur.next;
            ListNode b = a.next;
            cur.next = b;
            a.next = b.next;
            b.next = a;
            cur = a;
        }
        return node.next;
    }
}

//leetcode:143:重排链表
class Solution3 {
    public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null ){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode head2 = new ListNode(-1);
        ListNode cur = slow.next;
        slow.next = null;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = curN;
        }
        ListNode cur1 = head2.next;
        while(head != null && cur1 != null){
            ListNode headNext = head.next;
            ListNode curNext = cur1.next;
            head.next = cur1;
            cur1.next = headNext;
            head = headNext;
            cur1 = curNext;
        }
    }
}

//leetcode:23:合并k个升序链表
class Solution4 {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>((v1,v2) -> (v1.val - v2.val));
        for(ListNode list : lists){
            while(list != null){
                q.offer(list);
                list = list.next;
            }
        }
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(!q.isEmpty()){
            cur.next = q.poll();
            cur = cur.next;
        }
        cur.next = null;
        return head.next;
    }
}

//leetcode:25:k个一组翻转链表
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode pre1 = head;

        int count = 0;
        while(pre1 != null){
            count++;
            pre1 = pre1.next;
        }

        if(count < k){
            return head;
        }

        ListNode head1 = head;
        ListNode pre2 = head;
        ListNode cur = head.next;
        int x = k-1;
        while(x != 0){
            ListNode curN = cur.next;
            cur.next = pre2;
            pre2 = cur;
            cur = curN;
            x--;
        }
        head1.next = reverseKGroup(cur,k);
        return pre2;
    }
}
